//零钱兑换  力扣322
//完全背包 装满背包的最小物品数
class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		vector<int> dp(amount+1,INT_MAX);
		//初始化
		dp[0] = 0;
		//递推
		for(int i = 0; i < coins.size();i ++)
		{
			for(int j = coins[i]; j <= amount; j++)
			{   //先判断若考虑coins[i]的情况下，能不能凑成，若不能，则保留原来的值
				if(dp[j - coins[i]] != INT_MAX)
					dp[j] = min(dp[j],dp[j - coins[i]]+1);
			}
		}
		if(dp[amount] == INT_MAX) return -1;
		return dp[amount];
	}
};
